package sort;

import java.util.Arrays;
import java.util.Stack;

public class Sort {
    //插入排序
    public static void insertSort(int[] arr){
        //将数组分成两个区间，前为有序区间，后为无线区间
        //每次取出无序区间的第一个元素，插入到有序区间的合适位置
        for(int bound = 1; bound < arr.length; bound++){
            int val = arr[bound];   //记录无序区间第一个元素
            int cur = bound - 1;
            for(; cur >= 0; cur--){
                //将无序区间第一个元素从后往前与有序区间的元素逐个比较，当有序区间的
                // 元素大于无序区间第一个元素，将无序区间的元素后移一位
                if(arr[cur] > val){
                    arr[cur + 1] = arr[cur];
                }else{  //序区间的元素小于等于无序区间第一个元素时，找到无序区间第一个元素要插入的位置
                    break;
                }
            }
            //将无序区间第一个元素插入cur的后一个位置
            arr[cur + 1] = val;
            System.out.println(bound + " : " + Arrays.toString(arr));
        }
    }

    //希尔排序
    public static void shellSort(int[] arr){
        //根据gap值将数组分成多个组，针对每个组进行插入排序
        //此处的希尔序列，gap是 size/2, size / 4, size / 8 ...... 1
        for(int gap = arr.length / 2; gap >= 1; gap /= 2){
            insertSortGap(arr, gap);
            System.out.println("gap" + gap + ":" + Arrays.toString(arr));
        }
    }
    //插入排序
    public static void insertSortGap(int[] arr, int gap){
        for(int bound = gap; bound < arr.length; bound++){
            int val = arr[bound];   //记录待插入的元素
            int cur = bound - gap;
            for(; cur >= 0; cur -= gap){
                if(arr[cur] > val){
                    arr[cur + gap] = arr[cur];
                }else{
                    break;
                }
            }
            arr[cur + gap] = val;
        }
    }

    //选择排序
    //将数组分成有效区间[0, bound)和无序区间[bound, size)
    //从无序区间中选取最小的元素插入到有序区间的末尾
    public static void selectSort(int[] arr){
        for(int bound = 0; bound < arr.length - 1; bound++){
            int minIndex = bound;   //假设无序区间第一个元素是最小的，记录其下标
            for(int cur = bound + 1; cur < arr.length; cur++){
                //将记录下最小的元素与无序区间的其它元素比较，如果存在比最小元素还小，将该元素下标更新为最小元素的下标
                if(arr[minIndex] > arr[cur]){
                    minIndex = cur;
                }
            }
            //最小元素下标不等于无序区间的第一个元素，则进行交换
            if(minIndex != bound){
                int tmp = arr[bound];
                arr[bound] = arr[minIndex];
                arr[minIndex] = tmp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

    //堆排序
    //核心思想是建大堆（排升序），建完大堆后， 将堆顶元素与最后一个交换，
    // 然后进行向下调整，又变为长度为 size - 1 的大堆，如此循环得到升序数组
    public static void heapSort(int[] arr){
        //向下调整建大堆
        for(int parent = (arr.length - 1) / 2; parent >= 0; parent--){
            shiftDown(arr, arr.length, parent);
        }
        //将堆顶元素与最后一个元素交换，堆的长度逐渐减1，向下调整
        for(int cur = arr.length - 1; cur >= 1; cur--){
            swap(arr, 0, cur);
            shiftDown(arr, cur, 0);
            System.out.println(Arrays.toString(arr));
        }
    }
    //交换函数
    public static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    //向下调整
    public static void shiftDown(int[] arr, int size, int parent){
        int child = parent * 2 + 1;
        while(child < size){
            //没有右子树，则将父节点的值与左孩子的值进行比较
            //存在右孩子，取左右孩子较大的值与父亲结点进行比较
            if((child + 1) < size && arr[child] < arr[child + 1]){
                child++;
            }
            //孩子结点的值大于父亲结点的值，交换他们的值,更新父亲和孩子的下标
            if(arr[parent] < arr[child]){
                swap(arr, parent,  child);
            }else{  //parent处的值大于child处的值，不需要向下调整
                break;
            }
            parent = child;
            child = 2 * parent + 1;
        }
    }

    //冒泡排序
    //从前往后进行比较，[0，arr.length - i) 为无序区间，[arr.length - i， arr.length)为有序区间
    //一趟下来找到找到无序区间中最大的一个元素排到有序区间前一个的位置
    public static void bubbleSort(int[] arr){
        for(int i = 0; i < arr.length - 1; i++){
            boolean flag = true;
            for(int j = 1; j < arr.length - i; j++){
                if(arr[j -1] > arr[j]){
                    //未进行交换，则说明该无序区间是有序的了，这样整个数组都有序，排序完成
                    flag = false;
                    swap(arr, j - 1, j);
                }
            }
            System.out.println(Arrays.toString(arr));
            if(flag){
                break;
            }
        }
    }

    //递归快速排序的入口
    public static void quickSort(int[] arr){
        if(arr.length == 0){
            return;
        }

        quickSort(arr, 0, arr.length - 1);
    }
    //约定[left, right]为闭区间的待处理区间
    public static void quickSort(int[] arr, int left, int right){
        //空区间，或者只有一个元素的区间不用排序，一个元素是有序的
        if(left >= right){
            return;
        }
        //找到基准值所在数组中的位置的下标，并返回下标
        int index = partition(arr, left, right);
        //递归左半区间
        quickSort(arr, left, index - 1);
        //递归右半区间
        quickSort(arr, index + 1, right);
    }
    //三数取中，将第二大的数与最右边的数交换（第二的数是最左边的值，则不用交换）
    public static void midVal(int[] arr, int left, int mid, int right){
        if(arr[mid] > arr[right]){
            if(arr[left] > arr[mid]){
                swap(arr, left, mid);
            }else if(arr[right] > arr[left]){
                swap(arr, left, right);
            }
        }else{  // arr[mid] < arr[right]
            if(arr[left] < arr[mid]){
                swap(arr, left, mid);
            }else if(arr[right] < arr[left]){
                swap(arr, left, right);
            }
        }
    }
    public static int partition(int[] arr, int left, int right){
        int mid = left + (right - left) / 2;
        midVal(arr, left, mid, right);
        int value = arr[left];  //将最左边的值作为基准值
        int l = left;
        int r = right;
        //取最左边值为基准值，先从右边找小于基准值的元素，再从左边找大于基准值的元素，将他们进行交换
        while(l < r){
            //先从右边找小于基准值的元素
            while(l < r){
                if(arr[r] < value){
                    break;
                }
                r--;
            }
            //从左边找大于基准值的元素
            while(l < r){
                if(arr[l] > value){
                    break;
                }
                l++;
            }
            //将两个数进行交换
            if(l < r){
                swap(arr, l, r);
            }
        }
        //将基准值与相遇的数进行交换
        swap(arr, left, l);
        return l;
    }

    //区间类
    static class Range{
        public int left;
        public int right;

        public Range(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }
    //非递归排序，使用栈维护待排序的区间
    public static void quickSortByLoop(int[] arr){
        Stack<Range> stack = new Stack<>();
        //开展将整个数组入栈
        stack.push(new Range(0, arr.length - 1));

        while(!stack.isEmpty()){
            //弹出栈顶区间
            Range range = stack.pop();
            if(range.left >= range.right){
                //空区间或者只有一个元素的区间，不需要排序
                continue;
            }
            //使用partition整理区间的元素，返回基准值的下标
            int index = partition(arr, range.left, range.right);
            //左半区间入栈
            stack.push(new Range(range.left, index - 1));
            //右半区间入栈
            stack.push(new Range(index + 1, range.right));
        }
    }

    //递归 归并排序入口
    public static void mergeSort(int[] arr){
        mergeSort(arr, 0, arr.length - 1);
    }
    //辅助归并排序，引入子区间，约定[left, right]是闭区间
    public static void mergeSort(int[] arr, int left, int right){
        //区间内没有元素或者只有一个元素，不用排序
        if(left >= right){
            return;
        }
        //将[left, right]分成等长的两个区间，mid需要参加排序
        int mid = left + (right - left) / 2;
        //递归排序左半区间
        mergeSort(arr, left, mid);
        //递归排序右半区间
        mergeSort(arr, mid + 1, right);
        //上述两个区间有序后，针对这两个区间进行合并排序
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right){
        //创建大小为 right - left + 1 的空间
        int[] ret = new int[right - left + 1];
        int retSize = 0;
        int cur1 = left;
        int cur2 = mid + 1;
        //按顺序比较两个区间内的元素，小的元素尾插到数组ret中，下标增加1
        while(cur1 <= mid && cur2 <= right){
            if(arr[cur1] <= arr[cur2]){
                ret[retSize++] = arr[cur1++];
            }else {
                ret[retSize++] = arr[cur2++];
            }
        }
        //将剩余的元素尾插到ret中
        while(cur1 <= mid){
            ret[retSize++] = arr[cur1++];
        }
        while (cur2 <= right){
            ret[retSize++] = arr[cur2++];
        }
        //将ret中的元素拷贝会arr[left, right]区间内
        for(int i = 0; i < ret.length; i++){
            arr[left + i] = ret[i];
        }
    }

    //非递归归并排序，循环归并排序
    public static void mergeSortByLoop(int[] arr){
        //size表示要合并的数组的大小
        for(int size = 1; size < arr.length; size *= 2){
            //内部循环，进行两两合并
            for(int i = 0; i < arr.length; i += 2 * size){
                //取两个相邻且长度为size的数组进行合并，再取两个相邻且长度为size的数组进行合并，如此循环，直到取完整个数组
                // 合并的两个数组区间为[i, i + size - 1]，[i + size, i + 2*size - 1]

                //left = i 保证前一个区间的左界不会越界
                int left = i;
                //前一个区间的右界有可能越界，越界则右界等于arr.length - 1
                int mid = i + size - 1;
                if(mid >= arr.length - 1){
                    mid = arr.length - 1;
                }
                ////后一个区间的右界有可能越界，越界则右界等于arr.length - 1
                int right = i + 2 * size -1;
                if(right >= arr.length - 1){
                    right = arr.length - 1;
                }
                //合并两个数组
                merge(arr, left, mid, right);
                //System.out.println(Arrays.toString(arr));
            }
        }
    }
    //计数排序
    public static void countSort(int[] arr){
        int max = arr[0], min = arr[0];
        //找出数组中的最大值和最小值
        for(int num : arr){
            if(max < num){
                max = num;
            }
            if(min > num){
                min = num;
            }
        }
        //创建一个大小为 max - min + 1 的数组
        int[] count = new int[max - min + 1];
        //遍历数组进行统计
        for(int num : arr){
            count[num - min]++;
        }
        int index = 0;
        //将统计数组中的下标i+min放入arr数组中，得到升序的有序数组
        for(int i = 0; i < count.length; i++){
            for(int j = 0; j < count[i]; j++){
                arr[index++] = min + i;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{15,89,22,11,3,7,4,95,100,5,13,77,6,10,53};
        //insertSort(arr);
        //shellSort(arr);
        //selectSort(arr);

        //heapSort(arr);
        //bubbleSort(arr);
        //quickSort(arr);
        //quickSortByLoop(arr);
        //mergeSort(arr);
        //mergeSortByLoop(arr);
        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
